#include "SearchPlayer.h"

bool ChildSort(SearchChild child0, SearchChild child1)
{
	if(child0.HeuristicValue > child1.HeuristicValue)
		return true;
	return false;
}

// performes the minimax algorithum
int Minimax(GomokuBoard _current, int _depth, int _playerNum,
			  int _maxPlayer, EvaluationFunction _evaluationFunction)
{
	int t_opponentNum = OPPONENT(_playerNum); 

	//if _current is a termenal node or _depth is zero, return the heuristic of _current
	int t_outcome = _current.CheckForWin(t_opponentNum);
	if(_current.CheckForWin(t_opponentNum)) {
		if(t_opponentNum == _maxPlayer)
			return heuristicMax;
		else
			return heuristicMin;
	}
	else if(_depth == 0) {
		return _evaluationFunction(_current, _maxPlayer) - _evaluationFunction(_current, OPPONENT(_maxPlayer));
	}

	//otherwize, search lower...
	std::vector<Square> t_moves = _current.PossibleMoves(_playerNum);

	if(_playerNum == _maxPlayer) {
		int t_alpha = heuristicMin;
		for(std::vector<Square>::iterator iter = t_moves.begin(); iter < t_moves.end(); iter++)
		{
			GomokuBoard t_child(_current, *iter, _playerNum);
			int t_score = Minimax(t_child, _depth-1, t_opponentNum, _maxPlayer, _evaluationFunction);
			t_alpha = MAX(t_score, t_alpha);
		}
		return t_alpha;
	}
	else {
		int t_alpha = heuristicMax;
		for(std::vector<Square>::iterator iter = t_moves.begin(); iter < t_moves.end(); iter++)
		{
			GomokuBoard t_child(_current, *iter, _playerNum);
			int t_score = Minimax(t_child, _depth-1, t_opponentNum, _maxPlayer, _evaluationFunction);
			t_alpha = MIN(t_score, t_alpha);
		}
		return t_alpha;
	}
}

int AlphaBeta(GomokuBoard _current, int _depth, int _alpha, int _beta, int _playerNum,
			  int _maxPlayer, EvaluationFunction _evaluationFunction)
{
	int t_opponentNum = OPPONENT(_playerNum); 

	//if _current is a termenal node or _depth is zero, return the heuristic of _current
	/*Board t_board;
	std::list<Threat> t_threats;
	Move t_move;

	_current.GetBoard(t_board);
	FindAllThreats(_playerNum, t_board, t_threats);
	t_threats.sort(ThreatCompare);*/

	if(_current.CheckForWin(t_opponentNum)) {
		if(t_opponentNum == _maxPlayer)
			return heuristicMax;
		else
			return heuristicMin;
	}
	/*else if(FindThreatSequence(_playerNum, t_board, t_threats, 0, t_move) > -1)
	{
		if(_playerNum == _maxPlayer)
			return heuristicMax;
		else
			return heuristicMin;
	}*/
	else if(_depth == 0) {
		return _evaluationFunction(_current, _maxPlayer) - _evaluationFunction(_current, OPPONENT(_maxPlayer));
	}

	//otherwize do more serch'n
	std::vector<Square> t_moves = _current.PossibleMoves(_playerNum);
	std::list<SearchChild> t_children;

	for(int a = 0; a < t_moves.size(); a++)
	{
		SearchChild* t_newChild = new SearchChild;
		t_newChild->Board = _current;
		t_newChild->Board.Set(t_newChild->Move.x, t_newChild->Move.y, _playerNum);
		//t_newChild->HeuristicValue = _evaluationFunction(t_newChild->Board, _playerNum) - _evaluationFunction(t_newChild->Board, t_opponentNum);
		t_children.push_back(*t_newChild);
	}
	//t_children.sort(ChildSort);

	if(_playerNum == _maxPlayer) {
		for(std::list<SearchChild>::iterator iter = t_children.begin(); iter != t_children.end(); iter++)
		{
			_alpha = MAX(_alpha, AlphaBeta(iter->Board, _depth-1, _alpha, _beta, t_opponentNum,
				_maxPlayer,  _evaluationFunction));
			if(_beta <= _alpha) {
				//std::cout << "\tpruned!!\n";
				break;
			}
			//std::cout << "\t\t" << _playerNum << "(" << iter->x << "," <<  iter->y << "): a=" << _alpha << " b=" << _beta << "\n";
		}
		return _alpha;
	}
	else {
		//t_children.reverse();
		for(std::list<SearchChild>::iterator iter = t_children.begin(); iter != t_children.end(); iter++)
		{
			_beta = MIN(_beta, AlphaBeta(iter->Board, _depth-1, _alpha, _beta, t_opponentNum,
				_maxPlayer,  _evaluationFunction));
			if(_beta <= _alpha) {
				//std::cout << "\tpruned!!\n";
				break;
			}
			//std::cout << "\t" << _playerNum << "(" << iter->x << "," <<  iter->y << "): a=" << _alpha << " b=" << _beta << "\n";
		}
		return _beta;
	}
}

SearchPlayer::SearchPlayer(EvaluationFunction evaluationFunction, int searchDepth, bool alphaBeta)
{
	m_useAlphaBetaPruning = alphaBeta;
	m_evaluationFunction = evaluationFunction;
	m_searchDepth = searchDepth;
	m_moveNumber = 0;
}

SearchPlayer::~SearchPlayer()
{
}

void SearchPlayer::Play(int _player, Board board, Move &move)
{
	if(m_moveNumber == 0)
	{
		m_playedFirst = true;
		for(int a = 0; a < 19; a++)
		{
			for(int b = 0; b < 19; b++)
			{
				if(board[a][b] != 0) m_playedFirst = false;
			}
		}
	}

	if(m_playedFirst && m_moveNumber == 0)
	{
		// Play in center on first move
		move[0] = 9;
		move[1] = 9;
	}
	else
	{
		// Perform Search Algorithm
		int t_opponentNum = OPPONENT(_player);
		GomokuBoard t_current(board);
		std::vector<Square> t_moves = t_current.PossibleMoves(m_playerNum);
		std::list<SearchChild> t_children;

		for(int a = 0; a < t_moves.size(); a++)
		{
			SearchChild* t_newChild = new SearchChild;
			t_newChild->Move = t_moves[a];
			t_newChild->Board = t_current;
			t_newChild->Board.Set(t_newChild->Move.x, t_newChild->Move.y, _player);
			//t_newChild->HeuristicValue = m_evaluationFunction(t_newChild->Board, _player) - m_evaluationFunction(t_newChild->Board, t_opponentNum);
			t_children.push_back(*t_newChild);
		}
		//t_children.sort(ChildSort);

		int t_bestScore = heuristicMin;
		bool t_played = false; 
		for(std::list<SearchChild>::iterator iter = t_children.begin(); iter != t_children.end(); iter++)
		{
			int t_score = AlphaBeta((*iter).Board, m_searchDepth, t_bestScore, heuristicMax, t_opponentNum, _player, m_evaluationFunction);
			//int t_score = Minimax(t_child, 1, t_opponentNum, _player, m_evaluationFunction);
			if(t_score > t_bestScore)
			{
				t_bestScore = t_score;
				move[0] = iter->Move.x;
				move[1] = iter->Move.y;
				t_played = true;
			}
			//std::cout << "" << _player << "(" << iter->x << "," <<  iter->y << "): " << t_score << "\n";// << t_score << " t_abscore:" << t_abscore << "\n";
		}
		//std::cout << "move:" << _player << "(" << move[0] << "," <<  move[1] << "): " << t_bestScore << "\n";
		if(!t_played)
		{
			move[0] = t_moves.front().x;
			move[1] = t_moves.front().y;
		//	std::cout << "I forfit\n";
		}
	}

	m_moveNumber++;
}
